package com.lw.leetcode.binary.c;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

/**
 * Created with IntelliJ IDEA.
 * 2163. 删除元素后和的最小差值
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/11 17:16
 */
public class MinimumDifference {

    public static void main(String[] args) {
        MinimumDifference test = new MinimumDifference();

        // 1
//        int[] arr = {7, 9, 5, 8, 1, 3};

        // -2675
        int[] arr = {12, 6, 90, 78, 88, 16, 46, 97, 70, 63, 42, 21, 59, 25, 36, 27, 41, 91,
                65, 18, 49, 80, 40, 35, 62, 16, 47, 94, 62, 45, 2, 28, 65, 38, 65, 37, 29, 49,
                17, 89, 95, 32, 28, 93, 19, 84, 9, 18, 53, 93, 18, 80, 43, 6, 44, 53, 52, 43,
                70, 95, 59, 66, 71, 88, 13, 27, 73, 34, 9, 72, 77, 86, 88, 82, 75, 35, 71,
                31, 34, 55, 72, 74, 16, 51, 55, 5, 100, 38, 14, 1, 45, 6, 22, 32, 14, 100, 16,
                70, 24, 95, 3, 89, 84, 15, 21, 100, 30, 44, 68, 15, 66, 3, 5, 20, 86, 92, 45,
                52, 25, 18, 80, 86, 13, 52, 23, 61, 17, 68, 60, 84, 70, 99, 16, 10, 94, 58, 91,
                55, 6, 38, 51, 21, 90, 42, 68, 86, 62, 99, 31, 71, 24, 64, 42, 1, 45, 43, 37,
                87, 68, 3, 89, 2, 6, 22, 60, 80, 16, 87, 49, 37, 83, 76, 59, 16, 80, 94, 66,
                95, 54, 80, 9, 19, 46, 42, 99, 19, 79, 42, 62, 26, 62, 23, 14, 47, 51, 68,
                6, 63, 64, 67, 29, 36, 15, 32, 37, 90, 26, 88, 29, 63, 42, 87, 23, 42, 88, 78};

        // -1
//        int[] arr = {3, 1, 2};

        // -238
//        int[] arr = {18,30,22,29,30,21,19,50,23,13,11,24,6,9,49,19,15,13,34,13,34,44,2,16,14,47,4,16,25,31,11,16,31,43,18,32,39,5,23,10,48,31};

        // -164
//        int[] arr = {37,27,39,45,45,11,50,4,5,38,13,33,28,38,9,14,20,28,42,16,25,29,37,50,17,43,24,33,2,5};

        // -286
//        int[] arr = {23, 31, 44, 8, 42, 48, 41, 31, 42, 13, 13, 11, 39, 34, 7, 32, 25, 24, 18, 16, 12, 12, 7, 13, 46, 6, 11, 5, 25, 1, 1, 43, 4, 35, 33, 36, 6, 19, 23, 21, 21, 37, 25, 28, 9, 34, 1, 25, 41, 18, 15};
//


        long l = test.minimumDifference(arr);
        System.out.println(l);
    }


    private Map<Integer, Integer> map = new HashMap<>();

    public long minimumDifference(int[] nums) {
        int length = nums.length;
        int n = length / 3;
        int n2 = n << 1;
        long sum1 = 0L;
        int[] arr = new int[n2];
        System.arraycopy(nums, n, arr, 0, n2);
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> Integer.compare(b, a));
        for (int i = 0; i < n; i++) {
            sum1 += nums[i];
            priorityQueue.add(nums[i]);
        }
        Arrays.sort(arr);
        long sum2 = 0L;
        for (int i = n2 - 1; i >= n; i--) {
            sum2 += arr[i];
        }
        long min = sum1 - sum2;
        int index = n - 1;
        for (int i = n; i < n2; i++) {
            int v = nums[i];
            priorityQueue.add(v);
            sum1 += v;
            sum1 -= priorityQueue.poll();
            if (v < arr[index + 1] || v < -arr[index + 1]) {
                binary(arr, index, v);
            } else {
                sum2 -= v;
                while (true) {
                    if (arr[index--] > 0) {
                        sum2 += arr[index + 1];
                        break;
                    }
                }
            }
            min = Math.min(min, sum1 - sum2);
        }
        return min;
    }

    public void binary(int[] nums, int end, int target) {
        Integer index = map.get(target);
        if (index != null) {
            index++;
            map.put(target, index);
            nums[index] *= -1;
            return;
        }

        if (nums[0] == target) {
            map.put(target, 0);
            nums[0] *= -1;
            return;
        }

        int st = 0;
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            int item = nums[m];
            if (item < 0) {
                item *= -1;
            }
            if (item < target) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        index = st + 1;
        map.put(target, index);
        nums[index] *= -1;
    }


}
